#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int numDecodings(string s) {
        int len = s.size();
        int dp[101] = { 0 };
        dp[len] = 1;
        if (s[len - 1] != '0') dp[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--)
        {
            if (s[i] != '0')
            {
                dp[i] += dp[i + 1];
                if (s[i] == '1') dp[i] += dp[i + 2];
                if (s[i] == '2' && s[i + 1] <= '6') dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
};